package com.leetcode.array_matrix;

/**
 * @author Dennis Li
 * @date 2020/7/22 23:06
 */
public class FindDuplicate_287 {

    // 鸽笼原理
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int left = 1, right = n - 1;
        // 通过二分法来判定区间
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            // 记录比mid小的num的个数
            for (int num : nums) {
                if (num <= mid) count++;
            }
//            final long count1 = Arrays.stream(nums).filter(num -> num <= mid).count();

            // 如果总数比mid的值大，那么重复的数一定在左边
            if (count > mid) {
                // 这里注意上面的条件是<=那么这里应该是包含mid的
                right = mid;
            } else {
                // 否则在右边。而且是不包含mid
                left = mid + 1;
            }
        }
        return left;
    }

}
